DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2019.27

Online and Offline Algorithms for Circuit Switch Scheduling

Authors: Roy Schwartz, Mohit Singh, and Sina Yazdanbod

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract

Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shifts from one matching to a different one a fixed delay delta is incurred during which no data can be transmitted. For the offline version of the problem we present a (1-(1/e)-epsilon) approximation ratio (for any constant epsilon >0). Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.

Cite as

Roy Schwartz, Mohit Singh, and Sina Yazdanbod. Online and Offline Algorithms for Circuit Switch Scheduling. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.FSTTCS.2019.27,
  author =	{Schwartz, Roy and Singh, Mohit and Yazdanbod, Sina},
  title =	{{Online and Offline Algorithms for Circuit Switch Scheduling}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.27},
  URN =		{urn:nbn:de:0030-drops-115893},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.27},
  annote =	{Keywords: approximation algorithm, online, matching, scheduling}
}

Search Results

Documents authored by Yazdanbod, Sina

Online and Offline Algorithms for Circuit Switch Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message